package com.ljy.my_study.lintcode.最大的数;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/** 
* @author James
* @date 2019年5月5日 
*/
public class TestMain {
//	Given a list of non negative integers, arrange them such that they form the largest number.
//	The result may be very large, so you need to return a string instead of an integer.
//	Have you met this question in a real interview?  Yes
//	Problem Correction
//	Example
//	Example 1:
//
//	Input:[1, 20, 23, 4, 8]
//	Output:"8423201"
//	Example 2:
//
//	Input:[4, 6, 65]
//	Output:"6654"
//	Challenge
//	Do it in O(nlogn) time complexity.
	public static void main(String[] args) {
//		88889
//		88
//		88888890
//		88889088
		int[] nums= {1,20,23,4,8};
		long start=System.currentTimeMillis();
		System.out.println(largestNumber2(nums));
		System.out.println(System.currentTimeMillis()-start);
	}
	
	public static String largestNumber(int[] nums) {
		if(nums==null||nums.length==0) {
			return null;
		}
		List<Integer> list=new ArrayList<>();
		for(int n:nums) {
			list.add(n);
		}
		Collections.sort(list, new Comparator<Integer>() {
			@Override
			public int compare(Integer i1, Integer i2) {
				String aStr=i1.toString();
				String bStr=i2.toString();
//				BigDecimal bd1=new BigDecimal(aStr+bStr);
//				BigDecimal bd2=new BigDecimal(bStr+aStr);
//				return -bd1.compareTo(bd2);
				String str1=aStr+bStr;
				String str2=aStr+bStr;
				return -str1.compareTo(str2);
			}
		});
		System.out.println(list);
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<nums.length;i++) {
			if(list.get(0)==0) return "0";
			sb.append(list.get(i).toString());
		}
		return sb.toString();
	}
	
	public static String largestNumber2(int[] nums) {
		if(nums==null||nums.length==0) {
			return null;
		}
		List<Integer> list=new ArrayList<>();
		for(int n:nums) {
			list.add(n);
		}
		Collections.sort(list, new Comparator<Integer>() {
			@Override
			public int compare(Integer i1, Integer i2) {
				String aStr=i1.toString();
				String bStr=i2.toString();
				char[] aChar=(aStr+bStr).toCharArray();
				char[] bChar=(bStr+aStr).toCharArray();
				for(int i=0;i<aChar.length;i++) {
					if(aChar[i]>bChar[i]) {
						return -1;
					}else if(aChar[i]<bChar[i]) {
						return 1;
					}
				}
				return 0;
			}
		});
		System.out.println(list);
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<nums.length;i++) {
			if(list.get(0)==0) return "0";
			sb.append(list.get(i).toString());
		}
		return sb.toString();
	}
}
